﻿//目标:设计一个线性表，可以：
//1.快速随机访问原色
//2.插入、删除无需移动其他元素
//3.插入删除避免频繁创建/销毁元素结点造成GC触发

//using System;
//using System.Collections;
//using System.Collections.Generic;

//namespace GxFramework
//{
//    //This is a container that gives:
//    //  - Unique items
//    //  - Fast random removal
//    //  - Fast unique inclusion to the end
//    //  - Sequential access
//    //Downsides:
//    //  - Uses more memory
//    //  - Ordering is not persistent
//    //  - Not Serialization Friendly.

//    //We use a Dictionary to speed up list lookup, this makes it cheaper to guarantee no duplicates (set)
//    //When removing we move the last item to the removed item position, this way we only need to update the index cache of a single item. (fast removal)
//    //Order of the elements is not guaranteed. A removal will change the order of the items.

//    public class IndexedSet<T>:IList<T>
//    {
//        int _firstElementPos = 0;   //首元素的存储位置
//        int _lastElementPos = 0;    //尾元素的存储位置

//        readonly List<T> _list = new List<T>();//实际存储的元素
//        List<int> _prevAndNextPosList = new List<int>();//元素的前后元素位置

//        //前 、 后
//        void SetNext(int curPos, int nextPos)
//        {
//            int v = _prevAndNextPosList[curPos];

//            //设置curPos后置
//            var mask = 0xffff;
//            v &= (mask << 16);//保留前置
//            v |= (mask & nextPos);
//            _prevAndNextPosList[curPos] = v;

//            //设置nextPos前置
//            v = _prevAndNextPosList[nextPos];
//            v &= mask;//保留后置
//            v |= (mask & curPos) << 16;
//            _prevAndNextPosList[nextPos] = v;
//        }

//        int GetPrev(int pos)
//        {
//            int v = _prevAndNextPosList[pos];
//            var ret = (v >> 16) & 0xffff;
//            return ret;
//        }
        
//        int GetNext(int pos)
//        {
//            int v = _prevAndNextPosList[pos];
//            var ret = v & 0xffff;
//            return ret;
//        }
//        public void Add(T item)
//        {
//            _list.Add(item);
//            _prevAndNextPosList.Add(-1);

//            var len = this.Count;

//            if (len == 1)
//                _firstElementPos = len - 1;
//            else
//            {
//                SetNext(_firstElementPos,len-1);
//            }
//            _lastElementPos = len;
//        }
//        public bool Remove(T item)
//        {
//            int index;
//            if (_dict.TryGetValue(item,out index))
//            {
//                RemoveAt(index);
//                return true;
//            }
//            return false;
//        }
//        public IEnumerator<T> GetEnumerator()
//        {
//            throw new NotImplementedException();
//        }
//        IEnumerator IEnumerable.GetEnumerator()
//        {
//            return GetEnumerator();
//        }
//        public void Clear()
//        {
//            _list.Clear();
//            _prevAndNextPosList.Clear();
//            _firstElementPos = _lastElementPos = 0;
//        }
//        public bool Contains(T item)
//        {
//            int len = _list.Count;
//            for (int i = 0; i < len;++i )
//            {
//                if (item.Equals(_list[len]))
//                {
//                    return true;
//                }
//            }
//            return false;
//        }
//        public int Count { get { return _list.Count; } }
//        public int IndexOf(T item)
//        {
//            var pos = _firstElementPos;
//            while(pos >= 0)
//            {
//                var curItem = _list[pos];
//                if (curItem.Equals())
//                {
//                    return iter.Current.Key - _firstIndex;
//                }
//            }
//            return -1;
//        }
//        public void Insert(int index, T item)
//        {
//        }
//        public void RemoveAt(int index)
//        {
//            if (index >= this.Count)
//                return;

//            int prePos = -1;
//            int pos = _firstElementPos;
//            for (int i = 0; i < index;++i )
//            {
//                prePos = pos;
//                pos = GetNext(pos);
//            }

//            int nextPos = GetNext(pos);
//            T item = _list[index];
//            if (pos == this.Count - 1)
//            {
                
//                _list.RemoveAt(index);
//                _nextPosList.RemoveAt(index);
 
//            }
//            else
//            {
//                int replaceIndex = _list.Count - 1;
//                T replaceItem = _list[replaceIndex];
//                _list[index] = replaceItem;
//                _dict[replaceItem] = index;
//                _list.RemoveAt(replaceIndex);
//            }
//            if (prePos >= 0)
//            {
//                SetNext(prePos,nextPos);
//                SetPrev(nextPos,prePos);
//            }else
//                _firstElementPos = nextPos;
//        }
//        public T this[int index]
//        {
//            get { return _list[index]; }
//            set 
//            {
//                var curItem = _list[index];
//                _dict.Remove(curItem);

//                _list[index] = value;
//                _dict[value] = index;
//            }
//        }
//        public void RemoveAll(Predicate<T> match) 
//        {
//            int curIndex=0;
//            while (curIndex < _list.Count)
//            {
//                T item = _list[curIndex];
//                if (match(item))
//                {
//                    RemoveAt(curIndex);
//                }
//                else
//                    ++curIndex;
//            }
//        }
//        public void Sort(Comparison<T> sortFunction)
//        {
//            _list.Sort(sortFunction);
//            for (int i = 0; i < _list.Count; ++i)
//            {
//                T item = _list[i];
//                _dict[item] = i;
//            }
//        }
//    }
//}
